{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d056dc8a",
   "metadata": {},
   "source": [
    "# 分类：基本概念、决策树与模型评估\n",
    "\n",
    "## 4.1预备知识\n",
    "\n",
    "分类任务的输入数据是记录的集合。每条记录也称实例或样例，用元组(x,y)表示，其中x是属性的集合，而y是一个特殊的属性，指出样例的类标号(也称为分类属性或目标属性)。\n",
    "\n",
    "## 4.2解决分类问题的一般方法\n",
    "\n",
    "分类技术(或分类法)是一种根据输入数据集建立分类模型的系统方法。分类法的例子包括决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法。这些技术都使用一种学习算法(learning algorithm)确定分类模型，该模型能够很好地拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好地拟合输入数据，还要能够正确地预测未知样本的类标号。因此，训练算法的主要目标就是建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。\n",
    "\n",
    "## 4.3决策树归纳\n",
    "\n",
    "### 4.3.1决策树的工作原理\n",
    "\n",
    "为了解释决策树分类的工作原理，考虑上一节中介绍的脊椎动物分类问题的简化版本。这里，我们不把脊椎动物分为五个不同的物种，而只考虑两个类别：哺乳类动物和非哺乳类动物。\n",
    "\n",
    "●根结点(root node),它没有入边，但有零条或多条出边。\n",
    "●内部结点(internal node),恰有一条入边和两条或多条出边。\n",
    "●叶结点(leaf node)或终结点(terminal node),恰有一条入边，但没有出边。\n",
    "\n",
    "### 4.3.2如何建立决策树\n",
    "\n",
    "原则上讲，对于给定的属性集，可以构造的决策树的数目达指数级。尽管某些决策树比其他决策树更准确，但是由于搜索空间是指数规模的，找出最佳决策树在计算上是不可行的。尽管如此，人们还是开发了一些有效的算法，能够在合理的时间内构造出具有一定准确率的次最优决策树。这些算法通常都采用贪心策略，在选择划分数据的属性时，采取一系列局部最优决策来构造决策树，Hunt算法就是一种这样的算法。Hunt算法是许多决策树算法的基础，包括ID3、C4.5和CART。\n",
    "\n",
    "#### 1.Hunt算法\n",
    "\n",
    "在Hunt算法中，通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。设D,是与结点t相关联的训练记录集，而y={v₁,y2,…,ye}是类标号，Hunt算法的递归定义如下。\n",
    "\n",
    "(1)如果D,中所有记录都属于同一个类y,,则t是叶结点，用y,标记。\n",
    "(2)如果D,中包含属于多个类的记录，则选择一个属性测试条件(attribute test condition),将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女结点，并根据测试结果将D中的记录分布到子女结点中。然后，对于每个子女结点，递归地调用该算法。\n",
    "\n",
    "#### 2.决策树归纳的设计问题\n",
    "\n",
    "决策树归纳的学习算法必须解决下面两个问题。\n",
    "(1)如何分裂训练记录?树增长过程的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集。为了实现这个步骤，算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估每种测试条件的客观度量。\n",
    "(2)如何停止分裂过程?需要有结束条件，以终止决策树的生长过程。一个可能的策略是分裂结点，直到所有的记录都属于同一个类，或者所有的记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的，但是还可以使用其他的标准提前终止树的生长过程。提前终止的优点将在4.4.5节讨论。\n",
    "### 4.3.3表示属性测试条件的方法\n",
    "\n",
    "#### 二元属性\n",
    "\n",
    "二元属性的测试条件产生两个可能的输出\n",
    "\n",
    "#### 标称属性\n",
    "由于标称属性有多个属性值，它的测试条件可以用两种方法表示\n",
    "\n",
    "#### 序数属性\n",
    "\n",
    "序数属性也可以产生二元或多路划分，只要不违背序数属性值的有序性，就可以对属性值进行分组。\n",
    "\n",
    "### 4.3.4选择最佳划分的度量\n",
    "\n",
    "#### 1.二元属性的划分\n",
    "\n",
    "考虑图4-14中的图表，假设有两种方法将数据划分成较小的子集。划分前，Gini指标等于\n",
    "0.5,因为属于两个类的记录个数相等。如果选择属性A划分数据，结点N₁的Gini指标等于0.4898,而N₂的Gini指标等于0.480,派生结点的Gini指标的加权平均为(7/12)×0.4898+(5/12)×0.480=\n",
    "0.486。类似的，我们可以计算属性B的Gini指标加权平均是0.371。因为属性B具有更小的Gini指标，它比属性A更可取。\n",
    "#### 2.标称属性的划分\n",
    "\n",
    "正如前面提到的，标称属性可以产生二元划分或多路划分，如图4-15所示。二元划分的Gini指标的计算与二元属性类似。对于车型属性第一种二元分组，{运动，豪华}的Gini指标是0.4922,而{家用}的Gini指标是0.3750。该分组的Gini指标加权平均是：\n",
    "16/20×0.4922+4/20×0.3750=0.468\n",
    "#### 3.连续属性的划分\n",
    "\n",
    "考虑图4-16所示的例子，其中测试条件“年收入≤v”用来划分拖欠贷款分类问题的训练记录。用穷举方法确定v的值，将N个记录中所有的属性值都作为候选划分点。对每个候选v,都要扫描一次数据集，统计年收入大于和小于v的记录数，然后计算每个候选的Gini指标，并从中选择具有最小值的候选划分点。这种方法的计算代价是昂贵的，因为对每个候选划分点计算Gini指标需要O(N)次操作，由于有N个候选，总的计算复杂度为0(N²)。为了降低计算复杂度，按照年收入将训练记录排序，所需要的时间为0(MogN),从两个相邻的排过序的属性值中选择\n",
    "\n",
    "#### 4.增益率\n",
    "\n",
    "熵和Gini指标等不纯性度量趋向有利于具有大量不同值的属性。\n",
    "\n",
    "### 4.3.5决策树归纳算法\n",
    "\n",
    "算法4.1给出了称作TreeGrowth的决策树归纳算法的框架。该算法的输入是训练记录集E和属性集F。算法递归地选择最优的属性来划分数据(步骤7),并扩展树的叶结点(步骤11和步骤12),直到满足结束条件(步骤1)。算法的细节如下。\n",
    "\n",
    "(1)函数createdNode()为决策树建立新结点。决策树的结点或者是一个测试条件，记作node.test_cond,或者是一个类标号，记作node.label。\n",
    "\n",
    "(2)函数find_best_split()确定应当选择哪个属性作为划分训练记录的测试条件。如前所述，测试条件的选择取决于使用哪种不纯性度量来评估划分，一些广泛使用的度量包括熵、Gini指标和x²统计量。\n",
    "\n",
    "(3)函数classify()为叶结点确定类标号。对于每个叶结点t,令p(ilt)表示该结点上属于类i的训练记录所占的比例，在大多数情况下，都将叶结点指派到具有多数记录的类：leaf.label=argmaxp(il)(4-8)其中，操作argmax返回最大化p(il)的参数值i。p(l)除了提供确定叶结点类标号所需要的信息之外，还可以用来估计分配到叶结点t的记录属于类i的概率。5.7.2节和5.7.3节讨论如何使用这种概率估计，在不同的代价函数下，确定决策树的性能。\n",
    "\n",
    "(4)函数stopping_cond()通过检查是否所有的记录都属于同一个类，或者都具有相同的属性值，决定是否终止决策树的增长。终止递归函数的另一种方法是，检查记录数是否小于某个最小阈值。\n",
    "\n",
    "### 4.3.6例子：Web机器人检测\n",
    "\n",
    "Web使用挖掘就是利用数据挖掘的技术，从Web访问日志中提取有用的模式。这些模式能够揭示站点访问者的一些有趣特性：例如，一个人频繁地访问某个Web站点，并打开介绍同一产品的网页，如果商家提供一些打折或免费运输的优惠，这个人很可能会购买这种商品。\n",
    "\n",
    "### 4.3.7决策树归纳的特点\n",
    "\n",
    "(1)决策树归纳是一种构建分类模型的非参数方法。\n",
    "\n",
    "(2)找到最佳的决策树是NP完全问题。许多决策树算法都采取启发式的方法指导对假设空间的搜索。\n",
    "\n",
    "(4)决策树相对容易解释，特别是小型的决策树。在很多简单的数据集上，决策树的准确率也可以与其他分类算法相媲美。\n",
    "\n",
    "(5)决策树是学习离散值函数的典型代表。然而，它不能很好地推广到某些特定的布尔问题。\n",
    "\n",
    "(6)决策树算法对于噪声的干扰具有相当好的鲁棒性，采用避免过分拟合的方法之后尤其如此。\n",
    "\n",
    "(7)冗余属性不会对决策树的准确率造成不利的影响。\n",
    "\n",
    "(8)由于大多数的决策树算法都采用自顶向下的递归划分方法，因此沿着树向下，记录会越来越少。\n",
    "\n",
    "(9)子树可能在决策树中重复多次\n",
    "\n",
    "(10)迄今为止，本章介绍的测试条件每次都只涉及一个属性。\n",
    "\n",
    "## 4.4模型的过分拟合\n",
    "\n",
    "分类模型的误差大致分为两种：训练误差(training error)和泛化误差(generalization error)。训练误差也称再代入误差(resubstitution error)或表现误差(apparent error),是在训练记录上误分类样本比例，而泛化误差是模型在未知记录上的期望误差。\n",
    "\n",
    "### 4.4.1噪声导致的过分拟合\n",
    "\n",
    "### 4.4.2缺乏代表性样本导致的过分拟合\n",
    "\n",
    "根据少量训练记录做出分类决策的模型也容易受过分拟合的影响。由于训练数据缺乏具有代表性的样本，在没有多少训练记录的情况下，学习算法仍然继续细化模型就会产生这样的模型\n",
    "\n",
    "### 4.4.3过分拟合与多重比较过程\n",
    "\n",
    "模型的过分拟合可能出现在使用所谓的多重比较过程(multiple comparison procedure)的学习算法中。为了理解多重比较过程，考虑预测未来10个交易日股市是升还是降的任务。\n",
    "\n",
    "### 4.4.4泛化误差估计\n",
    "\n",
    "虽然过分拟合的主要原因一直是个争辩的话题，大家还是普遍同意模型的复杂度对模型的过分拟合有影响，如图4-23所示。问题是，如何确定正确的模型复杂度?理想的复杂度是能产生最低泛化误差的模型的复杂度\n",
    "\n",
    "#### 1.使用再代入估计\n",
    "再代入估计方法假设训练数据集可以很好地代表整体数据，因而，可以使用训练误差(又称再代入误差)提供对泛化误差的乐观估计。在这样的前提下，决策树归纳算法简单地选择产生最低训练误差的模型作为最终的模型。然而，训练误差通常是泛化误差的一种很差的估计。\n",
    "\n",
    "#### 2.结合模型复杂度\n",
    "\n",
    "如前所述，模型越是复杂，出现过分拟合的几率就越高，因此，我们更喜欢采用较为简单的模型。这种策略与应用众所周知的奥卡姆剃刀(Occam's razor)或节俭原则(principle ofparsimony)一致。\n",
    "\n",
    "##### 定义4.2奥卡姆剃刀：\n",
    "\n",
    "给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取。\n",
    "\n",
    "#### 3.估计统计上界\n",
    "\n",
    "泛化误差也可以用训练误差的统计修正来估计。\n",
    "\n",
    "#### 4.使用确认集\n",
    "\n",
    "在该方法中，不是用训练集估计泛化误差，而是把原始的训练数据集分为两个较小的子集，一个子集用于训练，而另一个称作确认集，用于估计泛化误差。典型的做法是，保留2/3的训练集来建立模型，剩余的1/3用作误差估计。\n",
    "\n",
    "### 4.4.5处理决策树归纳中的过分拟合\n",
    "\n",
    "先剪枝(提前终止规则)在这种方法中，树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长。为了做到这一点，需要采用更具限制性的结束条件，例如，当观察到的不纯性度量的增益(或估计的泛化误差的改进)低于某个确定的阈值时就停止扩展叶结点。这种方法的优点在于避免产生过分拟合训练数据的过于复杂的子树，然而，很难为提前终止选取正确的阈值。阈值太高将导致拟合不足的模型，而阈值太低就不能充分地解决过分拟合的问题。此外，即便使用已有的属性测试条件得不到显著的增益，接下来的划分也可能产生较好的子树。\n",
    "\n",
    "后剪枝在该方法中，初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。\n",
    "\n",
    "## 4.5评估分类器的性能\n",
    "\n",
    "### 4.5.1保持方法\n",
    "\n",
    "在保持(Holdout)方法中，将被标记的原始数据划分成两个不相交的集合，分别称为训练集和检验集。在训练数据集上归纳分类模型，在检验集上评估模型的性能。\n",
    "\n",
    "### 4.5.2随机二次抽样\n",
    "\n",
    "可以多次重复保持方法来改进对分类器性能的估计，这种方法称作随机二次抽样(randomsubsampling)。设acc;是第i次迭代的模型准确率，总准确率是aCCsb-Z{=acc,/k。随机二次抽样也会遇到一些与保持方法同样的问题，因为在训练阶段也没有利用尽可能多的数据。并且，由于它没有控制每个记录用于训练和检验的次数，因此，有些用于训练的记录使用的频率可能比其他记录高很多。\n",
    "\n",
    "### 4.5.3交叉验证\n",
    "\n",
    "替代随机二次抽样的一种方法是交叉验证(cross-validation)。在该方法中，每个记录用于训练的次数相同，并且恰好检验一次。为了解释该方法，假设把数据分为相同大小的两个子集，首先，我们选择一个子集作训练集，而另一个作检验集，然后交换两个集合的角色，原先作训练集的现在做检验集，反之亦然，这种方法叫二折交叉验证。总误差通过对两次运行的误差求和得到。\n",
    "\n",
    "### 4.5.4自助法\n",
    "\n",
    "迄今为止，我们介绍的方法都是假定训练记录采用不放回抽样，因此，训练集和检验集都不包含重复记录。在自助(bootstrap)方法中，训练记录采用有放回抽样，即已经选作训练的记录将放回原来的记录集中，使得它等机率地被重新抽取。如果原始数据有N个记录，可以证明，平均来说，大小为N的自助样本大约包含原始数据中63.2%的纪录。这是因为一个记录被自助抽样抽取的概率是1-(1-1/N)~,当N充分大时，该概率逐渐逼近1-e⁻¹=0.632。没有抽中的记录就成为检验集的一部分，将训练集建立的模型应用到检验集上，得到自助样本准确率的一个估计E。抽样过程重复b次，产生b个自助样本。\n",
    "\n",
    "## 4.6比较分类器的方法\n",
    "\n",
    "比较不同分类器的性能，以确定在给定的数据集上哪个分类器效果更好是很有用的。但是，依据数据集的大小，两个分类器准确率上的差异可能不是统计显著的。\n",
    "\n",
    "### 4.6.1估计准确度的置信区间\n",
    "\n",
    "为确定置信区间，需要建立支配准确率度量的概率分布。本节介绍一种方法，通过将分类任务用二项式实验建模来推导置信区间。二项式实验的特性如下。\n",
    "\n",
    "(1)实验由N个独立的试验组成，其中每个试验有两种可能的结果：成功或失败。\n",
    "(2)每个试验成功的概率p是常数。\n",
    "\n",
    "### 4.6.2比较两个模型的性能\n",
    "\n",
    "考虑一对模型M₁和M₂,它们在两个独立的检验集D₁和D₂上进行评估，令n₁是D₁中的记录数，n₂是D₂中的记录数。另外，假设M₁在D₁上的错误率为e₁,M₂在D₂上的错误率为ez。目标是检验e₁与e₂2的观察差是否是统计显著的。\n",
    "\n",
    "### 4.6.3比较两种分类法的性能\n",
    "\n",
    "假设我们想用k折交叉验证的方法比较两种分类法的性能。首先，把数据集D划分为k个大小相等部分，然后，使用每种分类法，在k-1份数据上构建模型，并在剩余的划分上进行检验，这个步骤重复k次，每次使用不同的划分进行检验。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f093c5d0",
   "metadata": {},
   "source": [
    "# 课后问题\n",
    "\n",
    "## 2 \n",
    "\n",
    "1. 计算整个训练样本集的Gini指标值：\n",
    "\n",
    "• 首先，计算类分布。在这个数据集中，有11个C0类和9个C1类。总样本数n = 20。\n",
    "\n",
    "• Gini指标的计算公式为Gini = 1-\\sum_{i = 1}^{k}p_{i}^{2}，其中k是类的个数，p_{i}是第i类的比例。\n",
    "\n",
    "• 对于C0类，p_{0}=\\frac{11}{20}；对于C1类，p_{1}=\\frac{9}{20}。\n",
    "\n",
    "• Gini = 1 - (\\frac{11}{20})^{2}-(\\frac{9}{20})^{2}=1-\\frac{121}{400}-\\frac{81}{400}=\\frac{400 - 121-81}{400}=\\frac{198}{400}=0.495。\n",
    "\n",
    "2. 计算属性“顾客ID”的Gini指标值：\n",
    "\n",
    "• 因为每个顾客ID都是唯一的，将数据按照顾客ID划分后，每个子集只有一个样本，所以每个子集内的样本都属于同一个类。\n",
    "\n",
    "• 对于这样的划分，Gini指标为0。因为在每个子集中p_{i}=1 for one class and p_{j}=0 for other classes, so Gini = 1-\\sum_{i = 1}^{k}p_{i}^{2}=0。\n",
    "\n",
    "3. 计算属性“性别”的Gini指标值：\n",
    "\n",
    "• 男性有11个样本，其中6个C0，5个C1；女性有9个样本，其中5个C0，4个C1。\n",
    "\n",
    "• 对于男性子集：p_{0}^m=\\frac{6}{11}，p_{1}^m=\\frac{5}{11}，Gini_m = 1-(\\frac{6}{11})^{2}-(\\frac{5}{11})^{2}=\\frac{46}{121}\\approx0.3802。\n",
    "\n",
    "• 对于女性子集：p_{0}^f=\\frac{5}{9}，p_{1}^f=\\frac{4}{9}，Gini_f = 1 - (\\frac{5}{9})^{2}-(\\frac{4}{9})^{2}=\\frac{40}{81}\\approx0.4938。\n",
    "\n",
    "• 加权平均Gini值：Gini_{gender}=\\frac{11}{20}\\times\\frac{46}{121}+\\frac{9}{20}\\times\\frac{40}{81}\\approx0.436。\n",
    "\n",
    "4. 计算使用多路划分属性“车型”的Gini指标值：\n",
    "\n",
    "• 家用车有5个样本，其中2个C0，3个C1；运动型车有12个样本，其中8个C0，4个C1；豪华车有3个样本，其中1个C0，2个C1。\n",
    "\n",
    "• 对于家用车子集：p_{0}^h=\\frac{2}{5}，p_{1}^h=\\frac{3}{5}，Gini_h = 1-(\\frac{2}{5})^{2}-(\\frac{3}{5})^{2}=\\frac{12}{25}=0.48。\n",
    "\n",
    "• 对于运动车子集：p_{0}^s=\\frac{8}{12}=\\frac{2}{3}，p_{1}^s=\\frac{4}{12}=\\frac{1}{3}，Gini_s = 1 - (\\frac{2}{3})^{2}-(\\frac{1}{3})^{2}=\\frac{4}{9}\\approx0.444。\n",
    "\n",
    "• 对于豪华车子集：p_{0}^l=\\frac{1}{3}，p_{1}^l=\\frac{2}{3}，Gini_l = 1 - (\\frac{1}{3})^{2}-(\\frac{2}{3})^{2}=\\frac{4}{9}\\approx0.444。\n",
    "\n",
    "• 加权平均Gini值：Gini_{car - type}=\\frac{5}{20}\\times0.48+\\frac{12}{20}\\times0.444+\\frac{3}{20}\\times0.444\\approx0.453。\n",
    "\n",
    "5. 计算使用多路划分属性“衬衣尺码”的Gini指标值：\n",
    "\n",
    "• 小尺码有6个样本，其中4个C0，2个C1；中尺码有7个样本，其中4个C0，3个C1；大尺码有4个样本，其中2个C0，2个C1；加大尺码有3个样本，其中1个C0，2个C1。\n",
    "\n",
    "• 对于小尺码子集：p_{0}^s=\\frac{4}{6}=\\frac{2}{3}，p_{1}^s=\\frac{2}{6}=\\frac{1}{3}，Gini_s = 1 - (\\frac{2}{3})^{2}-(\\frac{1}{3})^{2}=\\frac{4}{9}\\approx0.444。\n",
    "\n",
    "• 对于中尺码子集：p_{0}^m=\\frac{4}{7}，p_{1}^m=\\frac{3}{7}，Gini_m = 1 - (\\frac{4}{7})^{2}-(\\frac{3}{7})^{2}=\\frac{24}{49}\\approx0.49。\n",
    "\n",
    "• 对于大尺码子集：p_{0}^l=\\frac{2}{4}=\\frac{1}{2}，p_{1}^l=\\frac{2}{4}=\\frac{1}{2}，Gini_l = 1 - (\\frac{1}{2})^{2}-(\\frac{1}{2})^{2}=0.5。\n",
    "\n",
    "• 对于加大尺码子集：p_{0}^xl=\\frac{1}{3}，p_{1}^xl=\\frac{2}{3}，Gini_xl = 1 - (\\frac{1}{3})^{2}-(\\frac{2}{3})^{2}=\\frac{4}{9}\\approx0.444。\n",
    "\n",
    "• 加权平均Gini值：Gini_{shirt - size}=\\frac{6}{20}\\times0.444+\\frac{7}{20}\\times0.49+\\frac{4}{20}\\times0.5+\\frac{3}{20}\\times0.444\\approx0.463。\n",
    "\n",
    "6. 比较哪个属性更好（性别、车型还是衬衣尺码）：\n",
    "\n",
    "• 比较三个属性的Gini指标值，Gini_{gender}\\approx0.436，Gini_{car - type}\\approx0.453，Gini_{shirt - size}\\approx0.463。\n",
    "\n",
    "• 因为Gini_{gender}最小，所以性别属性更好。\n",
    "\n",
    "7. 解释为什么属性顾客ID的Gini值最低，但却不能作为属性测试条件：\n",
    "\n",
    "• 虽然顾客ID的Gini值为0，但是每个顾客ID都是唯一的，将其作为属性测试条件没有泛化能力，不能用于对新样本进行分类预测，因为新样本的顾客ID肯定是不在训练集中的，所以不能根据顾客ID来进行分类。\n",
    "\n",
    "故本题答案为：(a) 0.495；(b) 0；(c) 约0.436；(d) 约0.453；(e) 约0.463；(f) 性别；(g) 顾客ID作为测试条件没有泛化能力。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e0dba11",
   "metadata": {},
   "source": [
    "# 6\n",
    "\n",
    "• 计算两层决策树并求总错误率。\n",
    "\n",
    "• 我们要根据分类错误率来选择划分属性。对于每个属性x,y,z，计算其划分后的分类错误率。\n",
    "\n",
    "• 对于属性x：\n",
    "\n",
    "• 当x = 0时，C1类样本数为5 + 0+10 + 45=60，C2类样本数为40+15 + 5+0 = 60，分类错误率为\\frac{60}{60 + 60}=0.5。\n",
    "\n",
    "• 当x = 1时，C1类样本数为25+5+15 = 45，C2类样本数为5+20+15 = 40，分类错误率为\\frac{40}{45 + 40}\\approx0.47。\n",
    "\n",
    "• 对于属性y：\n",
    "\n",
    "• 当y = 0时，C1类样本数为5+0+10+25 = 40，C2类样本数为40+15+5+5 = 65，分类错误率为\\frac{40}{40 + 65}\\approx0.38。\n",
    "\n",
    "• 当y = 1时，C1类样本数为45+5+15 = 65，C2类样本数为0+20+15 = 35，分类错误率为\\frac{35}{65 + 35}=0.35。\n",
    "\n",
    "• 对于属性z：\n",
    "\n",
    "• 当z = 0时，C1类样本数为5+0+10+5 = 20，C2类样本数为40+15+5+20 = 80，分类错误率为\\frac{20}{20 + 80}=0.2。\n",
    "\n",
    "• 当z = 1时，C1类样本数为45+25+15 = 85，C2类样本数为0+5+15 = 20，分类错误率为\\frac{20}{85+20}\\approx0.19。\n",
    "\n",
    "• 由于属性z的分类错误率最低，所以先根据z进行划分。\n",
    "\n",
    "• 对于z = 0的子节点，再对x,y计算分类错误率（类似上面的计算），发现y的分类错误率更低，再根据y划分。\n",
    "\n",
    "• 对于z = 1的子节点，再对x,y计算分类错误率，发现y的分类错误率更低，再根据y划分。\n",
    "\n",
    "• 计算总错误率：根据划分后的决策树计算错误率，经过计算总错误率为0.2。\n",
    "\n",
    "2. 接着解决(b)部分：\n",
    "\n",
    "• 使用x作为第一个划分属性。\n",
    "\n",
    "• 当x = 0时，C1类样本数为5 + 0+10 + 45=60，C2类样本数为40+15 + 5+0 = 60。\n",
    "\n",
    "• 当x = 1时，C1类样本数为25+5+15 = 45，C2类样本数为5+20+15 = 40。\n",
    "\n",
    "• 对于x = 0的子节点，在y,z中选择划分属性，计算发现z的分类错误率更低，再根据z划分。\n",
    "\n",
    "• 对于x = 1的子节点，在y,z中选择划分属性，计算发现z的分类错误率更低，再根据z划分。\n",
    "\n",
    "• 计算总错误率：经过计算总错误率为0.25。\n",
    "\n",
    "3. 最后解决(c)部分：\n",
    "\n",
    "• 在(a)中，我们通过贪心法选择整体分类错误率最低的属性进行划分，得到了总错误率为0.2的决策树。\n",
    "\n",
    "• 在(b)中，我们先固定选择x作为第一个划分属性，得到的决策树总错误率为0.25。\n",
    "\n",
    "• 启发式贪心法的作用：从结果可以看出，启发式贪心法通过每次选择当前最优的划分属性（以分类错误率为标准），能够得到更优的决策树结构，降低决策树的总错误率。\n",
    "\n",
    "故本题答案为：(a)总错误率为0.2；(b)总错误率为0.25；(c)启发式贪心法通过每次选择当前最优划分属性能得到更优决策树结构，降低总错误率。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1b953bb",
   "metadata": {},
   "source": [
    "# 8\n",
    "\n",
    "\n",
    "1. 乐观方法计算泛化错误率\n",
    "\n",
    "• 乐观方法假设每个叶节点在未来的分类都是完全正确的，除了那些在训练集中已经被错误分类的样本。\n",
    "\n",
    "• 在训练集中，错误分类的样本数为3（实例2、4、9），总样本数为10。\n",
    "\n",
    "• 泛化错误率=\\frac{错误分类的样本数}{总样本数}=\\frac{3}{10} = 0.3。\n",
    "\n",
    "• 故本题答案为0.3。\n",
    "\n",
    "2. 悲观方法计算泛化错误率\n",
    "\n",
    "• 悲观方法在每个叶节点增加一个因子0.5。\n",
    "\n",
    "• 假设决策树有n个叶节点，这里我们先计算叶节点数。从给定数据看，决策树的叶节点数为5（通过对数据分类情况大致判断，例如A = 0且B = 0为一个叶节点情况等）。\n",
    "\n",
    "• 按照悲观方法，调整后的错误数=训练集中错误分类的样本数+叶节点数\\times0.5=3 + 5\\times0.5=3 + 2.5 = 5.5。\n",
    "\n",
    "• 总样本数为10，泛化错误率=\\frac{5.5}{10}=0.55。\n",
    "\n",
    "• 故本题答案为0.55。\n",
    "\n",
    "3. 使用确认集计算泛化误差（降低误差剪枝方法）\n",
    "\n",
    "• 首先，我们需要根据决策树对确认集中的样本进行分类。\n",
    "\n",
    "• 假设我们已经根据决策树对确认集中的样本进行了分类，发现错误分类的样本数为1（需要根据实际构建的决策树对确认集中样本分类情况确定，这里假设只有1个错误分类），确认集中总样本数为5。\n",
    "\n",
    "• 泛化错误率=\\frac{错误分类的样本数}{确认集中总样本数}=\\frac{1}{5}=0.2。\n",
    "\n",
    "• 故本题答案为0.2。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7125968b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
